home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / COUPON.TST / README.CPN < prev    next >
Text File  |  1996-01-05  |  4KB  |  109 lines
  1.  
  2. DESCRIPTION OF THE COUPON COLLECTOR'S TEST
  3.  
  4. Introduction
  5. ------------
  6.  
  7. This is a strange name for a test of random number generators.  It is
  8. a time-honored name, though, having been introduced by R.E. Greenwood
  9. in 1955 [G1].  A coupon is a set of numbers from zero
  10. to the upper limit of the number space.  For example, if integers
  11. modulo 16 comprise the number space, a coupon is the set of integers
  12. from 0 to 15.  The coupon collector's test counts the random numbers
  13. that must be generated to yield a coupon.  Mixed in with the set of
  14. coupon members will be repetitions.  The idea is to count everything
  15. until a "complete set" is found.  The count of random numbers generated
  16. is called the "length" of the segment that contains the coupon.
  17.  
  18. Since the length of a complete set must be at least the size of the
  19. coupon, the coupon collector's test tallies lengths that range from
  20. the length of the coupon to some maximum that you choose.  The
  21. algorithm for collecting data for the coupon collector's test is
  22. given on pages 62-63 of Knuth [K1].  The probabilities associated
  23. with the segment lengths are calculates as follows:
  24.  
  25.     Let d be the size of the number space and t be the maximum
  26.     segment length to be tallied.  That is, a coupon will consist
  27.     of numbers between 0 and d-1 and the maximum segment length
  28.     will be larger than d.  The number of categories in the test
  29.     is k = t - d + 1.  The probabilities are (from [K1, p. 63]):
  30.  
  31.            d! {r - 1}                        d!  {t - 1}   | [x] subscript x
  32.     p[r] = -- {     },  d <= r < t;  p[t] = -----{     }   | ^x exponent x
  33.           d^r {d - 1}                       d^t-1{  d  }   | the {} should
  34.                                    | be typed as a
  35.     where {} denotes a Stirling number of the second kind.     | Stirling number
  36.                                  see Knuth, p 63
  37. A Stirling number of the second kind, {k,r}, is the number of ways
  38. of partitioning k elements into r non-empty subsets ([H1], page 824).
  39.  
  40. The coupon test is implemented as program cupontst.  This program
  41. performs a Kolmogorov-Smirnov analysis on probabilities from 100
  42. chi-square tests.  The parameters that determine how the chi-square
  43. tests are performed are specified by you.  These parameters
  44. are read from the console unless you redirect the input device.
  45. As usual, prompts and messages are written to stderr and results
  46. are written to stdout.
  47.  
  48. Running the Coupon Test
  49. ----------------------
  50.  
  51. To start program cupontst, you can say simply
  52.  
  53.     cupontst
  54.  
  55. and you will be prompted for the required inputs.
  56.  
  57. Alternatively, you can say
  58.  
  59.     cupontst < [myfile.inp]
  60.  
  61. and the program will take its input data from myfile.inp.
  62.  
  63. Six input parameters are required:
  64.  
  65.     1.  Seed for the random number generator (-1 = Time of day)
  66.  
  67.            If you do not specify -1, the value entered must be less
  68.     than 65536.
  69.  
  70.     2.  Specification of generator to be tested
  71.  
  72.         If you are working interactively, you will see a list
  73.            of the generators that can be selected.  You enter the
  74.     character that represents your generator.  If you enter
  75.     a character that is not in the list, the library rand()
  76.     function will be used.
  77.  
  78.     3.    Number of unique integers in a coupon (d)
  79.  
  80.     This is the size of a coupon.  A coupon will consist of
  81.     numbers from 0 to d-1.  The program currently limits your
  82.     choice to the range 5-25.  These limits are defined in a
  83.     header file, cupndefs.h.
  84.  
  85.     4.    Maximum segment length (t)
  86.  
  87.     Segments lengths of t or larger will be tallied as segments
  88.     of length t.  The program currently limits your choice to
  89.     the range 11-100.  These limits are defined in a header file,
  90.     cupndefs.h.
  91.  
  92.     5.    Minimum cell expectation
  93.  
  94.     This is the minimum number of tallies that you want per
  95.     category ("cell" is a synonym for category).  This number
  96.     is used to determine the number of variates that should
  97.     be generated.  The program currently limits your choice
  98.     to the range 5-100.  The number 5 is specified because
  99.     it is the lowest number that is considered statistically
  100.     significant.
  101.  
  102. REFERENCE
  103.  
  104. G1. Robert E. Greenwood, Coupon Collector's Test for Random Digits,
  105.     Math. Tables & Other Aids to Computation, 9 (1955), pp. 1-4.
  106. H1. Handbook of Mathematical Tables, ed. by M. Abramowitz
  107.     and I. A. Stegun (Washington, D.C.: U.S. Gov't Printing
  108.     Office, 1964).
  109.